package com.duoduo;

import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

/**
 * @program: algorithm
 * @description: LUR本地缓存146
 * @author: chaidl  ！
 * @create: 2022-05-18 21:51
 */
public class LRUCache {
	//	此次LRU本地缓存采用map+双向链表的形式，并且采用头插法
	class LinkCacheNode {
		int key;
		int value;
		//前指针
		LinkCacheNode pre;
		//LinkCacheNode
		LinkCacheNode next;
	}
	
	//使用map存取数据，达到（o1)的效果
	private Map<Integer, LinkCacheNode> cache = new ConcurrentHashMap<>(64);
	//初始化一个前后指针
	LinkCacheNode head;
	LinkCacheNode tail;
	
	public LRUCache(int capacity) {
		head = new LinkCacheNode();
		//用head结点的key存放容量
		//value存放当前链表中结点的实际数量
		head.key = capacity;
		head.value = 0;
		head.pre = null;
		tail = new LinkCacheNode();
		tail.next = null;
		head.next = tail;
		tail.pre = head;
	}
	
	public int get(int key) {
		LinkCacheNode node = cache.get(key);
		if (node == null) {
			return -1;
		}
		//此处说明改值被访问过，要移动到头结点
		this.moveToHead(node);
		return node.value;
	}
	
	/**
	 * 存放数据
	 *
	 * @param key
	 * @param value
	 */
	public void put(int key, int value) {
		LinkCacheNode node = cache.get(key);
		if (node == null) {
			LinkCacheNode newCacheNode = new LinkCacheNode();
			newCacheNode.key = key;
			newCacheNode.value = value;
			this.cache.put(key, newCacheNode);
			this.addNode(newCacheNode);
			++head.value;
			if (head.value > head.key) {
				//	超出容量限制，移除尾结点
				LinkCacheNode tail = this.removeTail();
				this.cache.remove(tail.key);
				--head.value;
			}
		} else {
			//如果已经存在，就放入头结点
			node.value = value;
			this.moveToHead(node);
		}
	}
	
	/**
	 * 移除尾结点
	 *
	 * @return
	 */
	private LinkCacheNode removeTail() {
		LinkCacheNode oldNode = tail.pre;
		this.removeNode(oldNode);
		return oldNode;
	}
	
	/**
	 * 移动到头结点
	 *
	 * @param node
	 */
	private void moveToHead(LinkCacheNode node) {
		//先解除当前节点与链表的关系
		this.removeNode(node);
		//再加入头结点
		this.addNode(node);
	}
	
	/**
	 * 将当前节点加入
	 *
	 * @param node
	 */
	private void addNode(LinkCacheNode node) {
		node.pre = head;
		node.next = head.next;
		head.next.pre = node;
		head.next = node;
	}
	
	/**
	 * 从链表移除
	 *
	 * @param node
	 */
	private void removeNode(LinkCacheNode node) {
		LinkCacheNode oldNextNode = node.next;
		LinkCacheNode oldPreNode = node.pre;
		oldPreNode.next = oldNextNode;
		oldNextNode.pre = oldPreNode;
	}
}
